package com.offer;


import com.bean.TreeNode;
import com.sun.source.tree.Tree;
import com.utils.TreeUtils;

public class Test68_1 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode node = TreeUtils.buildTree("6,2,8,0,4,7,9,null,null,3,5");

        Test68_1 test = new Test68_1();
        System.out.println(test.lowestCommonAncestor(node, new TreeNode(7), new TreeNode(9)).val);
    }

}
